/**
 * 100. 相同的树
 *
 * 【简单】
 *
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg】
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 *
 * 示例 2：
 * 【https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg】
 * 输入：p = [1,2], q = [1,null,2]
 * 输出：false
 *
 * 示例 3：
 * 【https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg】
 * 输入：p = [1,2,1], q = [1,1,2]
 * 输出：false
 */

import { TreeNode } from '../utils/tree'

// 递归
var isSameTree = function isSameTree(
	p: TreeNode | null,
	q: TreeNode | null
): boolean {
	if (p == null && q == null) {
		return true
	}
	if (p == null || q == null) {
		return false
	}
	if (p.val !== q.val) {
		return false
	}

	return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

// 迭代
var isSameTree = function isSameTree(
	p: TreeNode | null,
	q: TreeNode | null
): boolean {
	if (p == null && q == null) {
		return true
	}

	const queue = [p, q]
	while (queue.length) {
		p = queue.shift() as TreeNode | null
		q = queue.shift() as TreeNode | null

		if (p == null && q == null) {
			continue
		}

		if (p != null || q != null) {
			return false
		}

		if (p!.val !== q!.val) {
			return false
		}

		queue.push(p!.left, q!.left)
		queue.push(p!.right, q!.right)
	}

	return true
}
